/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {

  // 深度优先遍历 
  // let res = false
  // function dfs(node, sum) {
  //   if (!node) return
  //   sum += node.val
  //   if (sum == targetSum && !node.left && !node.right) res = true
  //   else
  //     if (node.left) dfs(node.left, sum)
  //   if (node.right) dfs(node.right, sum)
  // }

  // dfs(root, 0)
  // return res

  // 广度优先遍历
  // let queue =[]
  // if(root) queue.push([root,root.val])
  // while(queue.length>0){
  //   let [node,sum] = queue.shift()
  //   if(sum==targetSum && !node.left && !node.right) return true
  //    if(node.left) queue.push([node.left,sum+node.left.val])
  //    if(node.right) queue.push([node.right,sum+node.right.val])
  // }
  // return false

  // 递归
  // let res = false
  function check(node, sum) {
    if (!node) return
    if (targetSum - sum === node.val && !node.left && !node.right) return true
    return check(node.left, sum + node.val) || check(node.right, sum + node.val)

  }

  return check(root,0)
};

